/* MC202 - Estruturas de dados - 2. semestre de 2005.
 * Fun�es para a montagem da �vore de codifica�o. */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "arvhuff.h"
#include "heap.h"

typedef struct fila{
  struct fila * prox;
  No * inf;
}fila;

/* Rotina auxiliar para compara�o das freq�cias das sub-�vores.
 * Retorna um valor menor que zero se arv1->freq < arv2->freq ou um
 * valor maior que zero se arv1->freq > arv2->freq.  Caso as
 * freq�cias sejam iguais, retorna um valor menor do que zero caso
 * arv1 contenha um caracter de valor ASCII menor que arv2, ou
 * retorna um valor maior do que zero caso contr�io.
 *
 * J�vem implementada e n� deve ser modificada.
 */
int compara_no(No *arv1, No *arv2) {
  if (arv1->freq != arv2->freq)
    return arv1->freq - arv2->freq;
  return arv1->c - arv2->c;
}

/* Fun�o que cria um n�vazio.
 *
 * J�vem implementada e n� deve ser modificada.
 */
No *cria_no_vazio() {
  No *no = (No*) malloc(sizeof(No));
  no->esq = no->dir = NULL;
  no->c = 0;
  no->freq = 0;
  return no;
}

No *cria_no(int c, int f) {
  No *no = calloc(1,sizeof(No));
  no->c = c;
  no->freq = f;
  return no;
}

/* Voc�deve implementar todas as fun�es abaixo. Se necess�io,
 * voc�pode criar fun�es auxiliares aqui. */
void pfila(fila **f, No * novo){//coloca na fila
  fila * n;
  if(!novo){return;}
  n=calloc(1,sizeof(fila));
  n->inf=novo;
  while(*f){
    if((((*f)->inf)->freq>novo->freq)||((((*f)->inf)->freq==novo->freq)&&(((*f)->inf)->c>novo->c))) {
      break;
    }
    f=&((*f)->prox);
  }
  n->prox=(*f);
  *f=n;
}
No * rfila(fila **f){//retira da fila
  if(!*f){return NULL;}
  fila * t;
  No * aux;
  t=(*f);
  *f=(*f)->prox;
  aux=t->inf;
  free(t);
  return aux;
}
void printfila(fila *f){//imprime fila
  if(!f){return;}
  while(f){
    printf("fila{%d %d} ",(f->inf)->c,(f->inf)->freq);
    f=f->prox;
  }
  printf("\n");
}
void gera_tabela_arvore_ax(No *arv,char **tab,int cam[100],int pos){
  if(!arv){return;}
  if((!arv->esq)&&(!arv->dir)){
    int c=0;
    tab[arv->c]=calloc(100,sizeof(char));
    tab[0][0]++;
    while(c<pos){
      tab[arv->c][c]=cam[c]+48;
      c++;
    }
  }else{
    cam[pos]=0;
    gera_tabela_arvore_ax(arv->esq,tab,cam,pos+1);
    cam[pos]=1;
    gera_tabela_arvore_ax(arv->dir,tab,cam,pos+1);
  }
  return;
}
/* Retorna um vetor de tamanho N_CHARS com a freq�cia dos caracteres do
 * arquivo fornecido. O �dice no vetor representa o valor ASCII de um
 * caracter. */
int *conta_frequencia_arquivo(FILE *arq) {
  int c;
  int * v;
  v=calloc(N_CHARS,sizeof(int));
  c=getc(arq);
  while((c>=0)&&(arq)){
    v[c]++;
    if(feof(arq)){return v;}
    c=getc(arq);
  }
  return v;
}


/* Faz a uni� de duas sub-�vores. O novo n�deve conter o caracter de
 * menor valor ASCII e a soma das freq�cias das sub-�vores. A sub-�vore
 * de menor freq�cia deve ficar �esquerda. Em caso de empate, a �vore
 * com o caracter de menor valor ASCII deve ficar �esquerda. */
No *merge_no(No *arv1, No *arv2) {
  No * n;
  if((!arv1) && arv2){
    return arv2;
  }else if((!arv2) && arv1){
    return arv1;
  }else if((!arv2) && (!arv1)){
    return NULL;
  }
  n=calloc(1,sizeof(No));
  n->freq=(arv1->freq)+(arv2->freq);
  if(arv1->c > arv2->c){
    n->c=arv2->c;
  }else{
    n->c=arv1->c;
  }
  if(arv1->freq==arv2->freq){
    if(n->c==arv1->c){
      n->esq=arv1;
      n->dir=arv2;
    }else{
      n->esq=arv2;
      n->dir=arv1;
    }
  }else if(arv1->freq<arv2->freq){
    n->esq=arv1;
    n->dir=arv2;
  }else{
    n->esq=arv2;
    n->dir=arv1;
  }
  return n;
}


/* Gera a �vore a partir de um arquivo. */
No *gera_arvore_arquivo(char *nomearq) {
//   fila * f;
  Heap * heap;
  No * aux;
  FILE * arq;
  int * freq;
  int c=0;
  arq=fopen(nomearq,"r");
  if(!arq){return NULL;}
  freq=conta_frequencia_arquivo(arq);
//----------------------------
//   while(c<N_CHARS){
//     if(freq[c]){
//       pfila(&f,cria_no(c,freq[c]));
// //       printfila(f);
//     }
//     c++;
//   }
//   if(f){
//     while(f->prox){
//       pfila(&f,merge_no(rfila(&f),rfila(&f)));
// //       printfila(f);
//     }
//   }
//   free(freq);
//   fclose(arq);
//   return rfila(&f);
//   -----------------------
  heap=cria_heap();
  while(c<N_CHARS){
    if(freq[c]){
//     printf("#%c %d#",c,freq[c]);
      insere_heap(heap,cria_no(c,freq[c]));
    }
    c++;
  }
  aux=NULL;
  while(!vazio_heap(heap)){
    if(aux){
      insere_heap(heap,aux);
      aux=NULL;
    }
    aux=merge_no(remove_menor_heap(heap),remove_menor_heap(heap));
  }
  free(freq);
  fclose(arq);
  destroi_heap(&heap);
  return aux;
}


/* Libera toda a mem�ia ocupada pela �vore. */
void destroi_arvore(No *arv) {
  if(!arv){return;}
  destroi_arvore(arv->esq);
  destroi_arvore(arv->dir);
  free(arv);
  return;
}


    
/* Retorna um vetor de strings de tamanho N_CHARS com a codifica�o de
 * Huffman dos caracteres. O �dice no vetor representa o valor ASCII de
 * um caracter. Quando um caracter n� possuir codifica�o, sua posi�o
 * no vetor deve conter NULL. arv aponta para a raiz da �vore. */
char **gera_tabela_arvore(No *arv) {
  char **tab;
  int cam[100];
  tab=calloc(N_CHARS,sizeof(void*));
  tab[0]=calloc(1,sizeof(char));
  gera_tabela_arvore_ax(arv,tab,cam,0);
  return tab;
}


/* Libera toda a mem�ia ocupada pela tabela. */
void destroi_tabela(char **tabela) {
  int c=0;
  while(c<N_CHARS){
    if(!tabela[c]){
      c++;
      continue;
    }
    free(tabela[c]);
    c++;
  }
  free(tabela);
}


/* Imprime a tabela de codifica�o. A primeira linha deve ser o nmero de
 * codifica�es. */
void imprime_tabela(char **tabela) {
  int c=1;
  printf("%d\n",tabela[0][0]);
  while(c<N_CHARS){
    if(!tabela[c]){
      c++;
      continue;
    }
    printf("%d %s\n",c,tabela[c]);
    c++;
  }
}


/* Insere o caracter c com codifica�o codif na �vore apontada por arv. */
void insere_arvore(No *arv, unsigned char c, char *codif) {
  int p=0;
  while((codif[p])&&(codif[p]!=10)){
    if(codif[p]==48){
      if(!arv->esq){arv->esq=cria_no_vazio();}
      arv=arv->esq;
    }else{
      if(!arv->dir){arv->dir=cria_no_vazio();}
      arv=arv->dir;
    }
    p++;
  }
  arv->c=c;
}

/*BBE foi utilizado nesse programa*/
